一個圖形具有兩個集合的基本組成:G(V,E)

• V:表示頂點的集合

    V(G1)={1,2,3,4}
  

• E:表示邊的集合

    E(G1)={(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(2,3)}
  

無向圖與有向圖

• 無向圖:圖的邊不具有方向性

    (V0,V1)=(V1,V0)
  

• 有向圖:圖的邊具有方向性

    <V0,V1>!=<V1,V0>
  

  <u,v>表示u-->v

        u是邊的尾巴
        v是邊的頭
  

圖的限制

• 自我邊:從同一個頂點出發，連接到自己
• 重複邊:兩個頂點重複連接

完全圖

一個圖形有最大的邊數量

設頂點數為n
    無向圖:n(n-1)
    有向圖:n(n-1)/2

鄰近與附接

子圖

屬於圖的子集合為子圖

路徑相關

路徑:從頂點到頂點所經過的邊

長度:路徑上的邊數目

除了第一個點和最後一個點，其餘經過頂點不重複為簡單路徑，當第一個點和最後一個點相同時可稱為迴圈。

強連結組件

強連結:在有向圖中，點u連向v，點v連向u

強連結組:具有強連結的最大子圖

分支度

該頂點附接的邊數量
有向圖:

• in-degree:以頂點作為箭頭的數量
• out-degree:以頂點作為箭尾的數量